#include "StdAfx.h"
#include "DoThi.h"
#include "vector"
#include "fstream"
#include "iostream"
using namespace std;

DoThi::DoThi(void)
{
}

DoThi::~DoThi(void)
{
}

void DoThi::DocFile(const char*input)
{
	int bientamthoi;
	fstream fin;
	//fin.open(input);
	fin.open("input.txt",ios::in);
	fin>>dinhxuatphat;
	fin>>sodinh;
	Matranbandau.KhoiTaoMaTran(sodinh);
	for(int i=0;i<Matranbandau.Matranke.size();i++)
	{
		for (int j=0;j<Matranbandau.Matranke.size();j++)
		{
			Matranbandau.Matranke[i][j]=0;
			if (fin)
			{
				fin>>bientamthoi;
				Matranbandau.Matranke[i][j]=bientamthoi;
			}
		}
	}
	fin.close();
}

void DoThi::GhiFile(const char*output)
{
	fstream fout;
	fout.open("output.txt",ios::out);
	duongdi[dinhxuatphat]=1;
	bool kq = TimChuTrinhHamilton(dem,dinhxuatphat);
	if(kq==true && Matranbandau.Matranke[duongdi[0]][duongdi[duongdi.size()-1]]!=0)
	{
		fout<<trongluongduongdi<<"\n";
		for (int i=duongdi.size()-1;i>=0;i--)
		{
			int temp=duongdi[i];
			fout<<temp<<" ";
		}
		cout<<"Co chu trinh Hamilton va da xuat ra file thanh cong!!!!!!!!!!!!!\n";
	}
	else
	{
		fout<<"NULL";
		cout<<"Khong co chu trinh Hamilton\n";
	}
	fout.close();
}

bool DoThi::TimChuTrinhHamilton(int dem,int x)
{
	if(dem==sodinh)
	{
		return true;//Co duong di hamilton
	}
	for(int i=0;i<sodinh;i++)
	{
		if(Matranbandau.Matranke[x][i]!=0&&Mangnhan[i]==0)
		{
			duongdi[dem]=i;//luu lai duong di
			trongluongduongdi+=Matranbandau.Matranke[x][i];
			Mangnhan[i]=1;//Danh dau da ghe tham dinh i
			if (TimChuTrinhHamilton(dem+1,i))//Tim thay chu trinh
			{
				return true;
			}
			Mangnhan[i]=0;//Bo danh dau da ghe tham dinh i
		}
	}
	return false;
}
